"""
题目描述
类似于力扣475，题面如下：
冬季已经来临。 你的任务是设计一个有固定加热半径的供暖器向所有房屋供暖。
在加热器的加热半径范围内的每个房屋都可以获得供暖。
现在，给出位于一条水平线上的房屋 houses 和供暖器 heaters 的位置，请你找出并返回可以覆盖所有房屋的最小加热半径。
输入:  houses = [1,2,3], heaters = [2]
输出:  1
解释
仅在位置2上有一个供暖器。如果我们将加热半径设为1，那么所有房屋就都能得到供暖。

每个工位去找最近的消毒工具，所有工位需要的距离的最大值即为答案。
"""


class Solution:
    def main(self, works, sters):
        r = 0
        nw = len(works)
        ns = len(sters)
        s = 0
        for w in range(nw):
            # 找sters[s]【即下一个消毒器】右边最近的消毒器（可能不存在）
            while s < ns and sters[s] < works[w]:
                s += 1

            # [1, 3, 5], [2]
            # 右边有消毒器，sters[s] >= works[w]
            if s < ns:
                d = sters[s] - works[w]
                if s - 1 >= 0:
                    # 左边有消毒器，且必有sters[s-1] < works[w]
                    d = min(d, works[w] - sters[s - 1])
            else:
                # 右边没消毒器，s == ns
                d = works[w] - sters[s - 1]
            if r < d:
                r = d
        return r


class Solution1:
    def main(self, works, sters):
        return 1


if __name__ == "__main__":
    A = Solution()
    print(A.main([1, 3, 5], [2, 3]))
    A = Solution1()
    print(A.main([1, 3, 5], [2]))
